package violentRecursion;

import org.junit.Test;

/**
 * @className: LeetCode_72
 * @Description: 编辑距离
 * @author: kunkun
 * @date: 2025/5/17 13:14
 */
public class LeetCode_72 {

    @Test
    public void test(){
        System.out.println(minDistance("horse","ros"));
    }


    public int minDistance(String word1, String word2) {
        return solution_2(word1,word2,0,0);
    }

    /**
     * @Author kunkun
     * @Description 暴力递归
     * @Date 14:00 2025/5/17
     * @Param
     * @return
     **/
    private int solution_1(String word1, String word2, int i, int j) {
        //1. 截止条件判断
        if (i==word1.length()){
            return word2.length()-j;
        }
        if (j==word2.length()){
            return word1.length()-i;
        }
        //2. 递归循环
        int res1 =Integer.MAX_VALUE,res2=Integer.MAX_VALUE,res3=Integer.MAX_VALUE,res4=Integer.MAX_VALUE;
        if (word1.charAt(i)==word2.charAt(j)){
            res1=solution_1(word1,word2,i+1,j+1);
        }else {
            res2 = 1+ solution_1(word1,word2,i,j+1);    //插入
            res3 = 1+ solution_1(word1,word2,i+1,j);  //删除
            res4 = 1+ solution_1(word1,word2,i+1,j+1);  //替换
        }
        return Math.min(Math.min(res1,res2),Math.min(res3,res4));
    }

    /**
     * @Author kunkun
     * @Description 动态规划
     * @Date 14:00 2025/5/17
     * @Param
     * @return
     **/
    private int solution_2(String word1, String word2, int x, int y) {
        //1. 定义变量
        int[][] dp = new int[word1.length()+1][word2.length()+1];
        //2. 设置初值
        for (int i = 0; i < word1.length()+1; i++) {
            dp[i][word2.length()] = word1.length()-i;
        }
        for (int j = 0; j < word2.length()+1; j++) {
            dp[word1.length()][j] = word2.length()-j;
        }
        //3. dp循环
        for (int i = word1.length()-1; i >=0 ; i--) {
            for (int j = word2.length()-1; j >=0 ; j--) {
                int temp = Integer.MAX_VALUE;
                if (word1.charAt(i)==word2.charAt(j)){
                    temp = Math.min(dp[i+1][j+1],temp);
                }else {
                    temp = Math.min(1+dp[i+1][j],temp);
                    temp = Math.min(1+dp[i][j+1],temp);
                    temp = Math.min(1+dp[i+1][j+1],temp);
                }
                dp[i][j] = temp;
            }
        }
        return dp[0][0];

    }

}
